#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (s[i] == s[j])
                    dp[i][j] = i <= j + 1 ? true : dp[i - 1][j + 1];
        for (int i = 1; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if (dp[n - 1][j] && dp[j - 1][i] && dp[i - 1][0])
                    return 1;
        return 0;
    };
};
// 1
// 0 1
// 0 0 1
// 0 1 0 1
// 0 0 0 0 1
// 0 0 0 0 1 1

// 1
//   1   
//         1